In the prior art there are numerous possible uses for autonomously operating mobile units. In this connection, one thinks of remote sensing probes, of mobile units which operate in danger areas, of self-propelled industrial vacuum cleaners, of transport vehicles in the production industry and, not least, of self-propelled robots. However, in order to be able to fulfil a practical task in an a priori unknown environment, an autonomous mobile robot must be able both to construct a reliable map of its working environment step by step and to locate itself at any given time using this map. Because of the very complex and unstructured environments in which such self-propelled units may possibly manoeuvre, their areas of use often remain restricted to office and domestic environments. Since in general an a priori map is not available, such a self-propelled unit must be equipped with sensors which allow the unit to interact in a flexible manner with its environment. Some such sensors are laser distance scanners, video cameras and ultrasonic sensors, for example.
A particular problem of these mobile units is that the formation of the environment map and the locating of the mobile unit depend on each other. In the process, various errors occur. On the one hand, such a mobile unit measures the distance covered from a starting position, on the other hand it uses distance sensors to measure the distance to obstacles which occur and enters these as landmarks in the environment map. Since these errors accumulate and add up over relatively long distances, practical manoeuvrability of the mobile unit is no longer given above a specific limit.
Previous solution formulations for this problem are based on the fact that characteristic landmarks in the environment are detected and their positions relative to the mobile unit are measured. From these relative positions of the landmarks and the absolute position of the unit, the absolute locations of the landmarks are determined. All the sensor measurements are generally affected by uncertainties. For this reason, methods are used with which the best possible estimation for the position of the mobile unit and the positions of the landmarks are found at the same time. Previously there has been a wide variety of formulations for solving this problem.
In a method by Leonard and Durrant-Whyte Directed Sonar Sensing for Mobile robot Navigation (pp. 51-65; pp. 97-111; pp. 129-138); Kluwer Academic Publishers, Boston, London, Dordrecht, 1992, the uncertainty relations between the landmarks and the mobile unit are not taken into account. Thus, on the one hand, the computing time is drastically reduced but, on the other hand, the errors between the predicted and measured sensor values cannot be assigned to the respective error sources. In order to ensure stability of the method, it is necessary to presuppose that the mobile unit can detect landmarks very accurately when stationary. Very accurate sensors are thus required, which in turn, because of their high costs, also limit the practical use of this method formation.
General statements about map building and about the motion of mobile units in cartographic environments can be taken from Y. Bar-Shalom and T. E. Fortmann, Tracking and Data Association (pp. 52-61; pp. 100-109). Academic Press, 1988 Directed Sonar Sensing for Mobile robot Navigation (pp. 51-65; pp. 97-111; pp. 129-138); Kluwer Academic Publishers, Boston, London, Dordrecht, 1992.
In order that a mobile robot can determine its position within its environment, the current sensor measurements must be correlated with an internal map, that is to say it must be decided which measurement agrees with which landmark in the map. From the assignment, the current robot position can then be estimated. If the solutions which are used result in few erroneous measurements, it is possible to find an assignment for each measurement. If, however, erroneous measurement often occur, it is only possible to-assign those measurements which, with high probability, agree with a landmark. For this purpose, a so-called validation gate method Y. Bar-Shalom and T. E. Fortmann, Tracking and Data Association (pp. 52-61; pp. 100-109), Academic Press, 1988; and Directed Sonar Sensing for Mobile robot Navigation (pp. 51-65; pp. 97-111; pp. 129-138); Kluwer Academic Publishers, Boston, London, Dordrecht, 1992 is used. This method calculates, on the basis of the difference between the measurement and the predicted measurement of the associated landmark and its respective uncertainties, the probability that the assignment is correct. For example, only those assignments whose statistical distance lies below a specific limit are accepted. If this limit is small, only very statistically closely adjacent, and thus extremely certain, assignments are allowed. If the differences between the measurements and the predicted measurements of the associated landmarks remain small over time, this functions very well. In a real environment, however, this rapidly leads to problems if landmarks are hidden by unknown objects. As long as the landmarks are hidden, no assignments are made in a correct manner. If, thereafter, the landmarks become visible once more, it may be the case that the estimated robot position has in the meantime become so erroneous, because of the slip of the drive wheels, that assignment can no longer be carried out because of the strict criterion, and the self-propelled mobile unit finally becomes lost in its environment. On the other hand, if this limit is selected to be too large, improbable assignments will also be allowed. The risk that false assignments will then be made is very large, with the consequence that disastrous errors which cannot be eliminated again later can be made in determining the position of the unit. In the solutions cited, on the basis of empirical experience, the parameter is selected such that an acceptable assignment is carried out in most cases.